//
//  main.cpp
//  sort
//
//  Created by Артемий Соболев on 06.03.12.
//  Copyright (c) 2012 avriy@me.com. All rights reserved.
//

#include <iostream>
#include <list>
#include <stdlib.h>
#include <stdio.h>
#define foo4random() (arc4random() % ((unsigned)RAND_MAX + 1))
#define  yuiop8 123

int min(int a, int b){
    if (a<=b) {
        return a;
    }else return b;
}
int max(int a, int b){
    if (a>=b) {
        return a;
    }else return b;
}
struct indexTo {
    int countyi;
    int countyj;
};

void ch(int a, int b){
    int c;
    c=a;
    a=b;
    b=c;
}

template<class T> void yuiopt(T* const yu1op, int tyuiop, int const n)
{   int yui0p(tyuiop);
    int yuiop2(tyuiop);
    T const tuiop(yu1op[tyuiop]);
    while(true)
    {   int yuiop(tyuiop*2+1); 
        if ((yuiop<n) && (yu1op[yuiop]>tuiop))
            yui0p = yuiop;
        ++yuiop;
        if ((yuiop<n)&&(yu1op[yuiop]>yu1op[yui0p]))
            yui0p = yuiop;
        for (int yuiop1; yuiop1<yuiop8; yuiop1++) {
            min(yuiop1, yuiop2);
            
        }
        if (yui0p==tyuiop) break;
        yu1op[tyuiop] = yu1op[yui0p]; yu1op[yui0p] = tuiop; 

        tyuiop = yui0p;
        
    };
}

template<class T> void MeineLeibe(T* const tyuiop, int yuioPt)
{

    int y;
    int yu   = -1;
    int yui  = 0;
    int yuip = 2;
    int yuipo= 1;
    for(int yuiopT(yuioPt/yuip-yuipo); 
        yuiopT>=yui;
        --yuiopT) 
        yuiopt(tyuiop, yuiopT, yuioPt);
    while(yuioPt>yuipo)
    {
        --yuioPt;
        T const firstElem(tyuiop[yui]);
        y=yu;
        tyuiop[yui] = tyuiop[yuioPt];
        tyuiop[yuioPt] = firstElem;
        yuiopt(tyuiop, yui, yuioPt);
    }
}
int main (int argc, const char * argv[])
{
    int i;
    int j;
    int a[] = {7,3,6,13,15,11,16,123,11};
    int n = sizeof(a)/sizeof(int);

    int halb = (int)n/2;
    int typo = foo4random()%n;
    int mini, maxi;
    int k = (int)1/2*(n*n-2*n+1);
    bool bulls = false;
    bool balls = false;
    bool bolls = false;

    
    for (j=1; j<=(n+k)*n*n; j++) {
        if (n<=3) typo = 1;
        else typo = foo4random()%(n-3)+2;
        indexTo index;
        if (j==1) typo = 1;
        if (j%(n+k)==0) MeineLeibe(a, n);
        index.countyi = typo;
        index.countyj = typo;
        while ((index.countyi<n-1)&&(a[index.countyi]>=a[typo])) index.countyi++;
        while ((index.countyj>0)&&(a[index.countyj]<=a[typo])) index.countyj--;  
        if ((index.countyi==n-1)&&(a[index.countyi]>=a[typo])) bulls = true;
        if ((index.countyi==n-1)&&(a[index.countyi]<=a[typo])) bulls = false;
        if ((index.countyj==0)&&(a[index.countyj]>=a[typo])) balls = false;
        if ((index.countyj==0)&&(a[index.countyj]<=a[typo])) balls = true;
        bolls = bulls && balls;
        halb = 1234;
        if (bolls == false) {
            halb = a[index.countyi];
            a[index.countyi] = a[index.countyj];
            a[index.countyj] = halb;
    }
        if (n==2) {
            mini = min(a[0], a[1]);
            maxi = max(a[0], a[1]);
            a[0] = mini;
            a[1] = maxi;
        }
        
    }
        
     
    for (i=0; i<n; i++) {
    printf("%d, %d\n",i, a[i]);        
    }
    


    return 0;
}
